class code3 {
    //N 皇后
    List<List<String>> ret;
    char[][] path;
    int n;
    boolean[] checkCol;//检测列
    boolean[] checkDig1;
    boolean[] checkDig2;
    public List<List<String>> solveNQueens(int _n) {
        n = _n;
        ret = new ArrayList<>();
        path = new char[n][n];
        checkCol = new boolean[n];
        checkDig1 = new boolean[2*n];
        checkDig2 = new boolean[2*n];
        for(int i=0;i<n;i++) {
            Arrays.fill(path[i],'.');
        }
        dfs(0);
        return ret;
    }
    void dfs(int row) {
        //出口
        if(row == n) {
            List<String> tmp = new ArrayList<>();
            for(int i=0;i<n;i++) {
                tmp.add(new String(path[i]));
            }
            ret.add(tmp);
        }
        for(int col=0;col<n;col++) {
            //符合条件就可继续
            if(checkCol[col]==false && checkDig1[row-col+n]==false && checkDig2[row+col]==false) {
                checkCol[col] = checkDig1[row-col+n] = checkDig2[row+col] = true;
                path[row][col] = 'Q';
                dfs(row+1);
                //恢复现场
                checkCol[col] = checkDig1[row-col+n] = checkDig2[row+col] = false;
                path[row][col] = '.';
            }
        }
    }
}